package com.zhang.study.chapter06;

import lombok.Data;

import java.util.Arrays;

@Data
public class Code01_Heap {

    /**
     * 堆的实现
     */
    private int[] heap;
    /**
     * 堆中元素的个数
     */
    private int heapSize;

    /**
     * 容量
     */
    private int capacity;

    public Code01_Heap(int capacity) {
        this.capacity = capacity;
        this.heap = new int[capacity];
        this.heapSize = 0;
    }

    /**
     * 判断堆是否为空
     *
     * @return true:为空 false:不为空
     */
    public boolean isEmpty() {
        return heapSize == 0;
    }

    /**
     * 判断堆是否满了
     *
     * @return true:满了 false:没满
     */
    public boolean isFull() {
        return heapSize == capacity;
    }

    public void push(int value) {
        if (isFull()) {
            throw new RuntimeException("堆满了");
        }
        heap[heapSize] = value;
        heapInsert(heap, heapSize++);
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("堆为空");
        }
        int ans = heap[0];
        heap[0] = heap[--heapSize];
        heapify(heap, 0, heapSize);
        return ans;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("堆为空");
        }
        return heap[0];
    }

    public void heapify(int[] arr, int index, int heapSize) {
        int left = index << 1 + 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index << 1 + 1;
        }
    }

    public void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        System.out.println(-1 / 2);
        Code01_Heap heap = new Code01_Heap(10);
        heap.push(3);
        heap.push(1);
        heap.push(5);
        System.out.println(Arrays.toString(heap.getHeap()));
    }


}
